//
// Created by wenyaxi on 24-11-14.
//
#include <common.h>

class Solution {
public:
    int maximumBags(vector<int> &capacity, vector<int> &rocks, int additionalRocks) {
        vector<int> diff(capacity.size(), 0);
        for (int i = 0; i < rocks.size(); i++) {
            diff[i] = capacity[i] - rocks[i];
        }
        ranges::sort(diff, less<>());
        int res = 0;
        int idx = 0;
        while (idx < diff.size() && additionalRocks > 0) {
            if (diff[idx] == 0) {
                res++;
                idx++;
            } else {
                int min_val = min(diff[idx], additionalRocks);
                diff[idx] -= min_val;
                additionalRocks -= min_val;
            }
        }
        while (idx < diff.size()) {
            if (diff[idx] == 0) {
                res++;
                idx++;
            }else {
                break;
            }
        }
        return res;
    }
};

void test() {
    /*[2,3,4,5]
[1,2,4,4]
2
[10,2,2]
[2,2,0]
100*/
    auto s = new Solution();
    vector<int> capacity{2, 3, 4, 5};
    vector<int> rocks{1, 2, 4, 4};
    constexpr int additionalRocks = 2;
    int maximum_bags = s->maximumBags(capacity, rocks, additionalRocks);
    printf("%d\n", maximum_bags);
}

void test1() {
    priority_queue<int, vector<int>, greater<> > pq;
    pq.push(1);
    pq.push(0);
    pq.push(1);
    pq.push(0);
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

int main(int argc, char *argv[]) {
    test();
}
